package dotdashdot.bradz.trendsettr;

import java.util.ArrayList;
import java.util.Collections;

public class ClassLevenshteinDistance {
	
	ArrayList<String> current_trends;
	public ClassLevenshteinDistance(ArrayList<String> current_trends){
		this.current_trends = new ArrayList<String>(current_trends);
	}
	
	public ArrayList<String> compareTrend(String trend, int distance){
		ArrayList<String> similar_words = new ArrayList<String>();
		for(String db_trend: current_trends){
			if(levenshteinDistance(trend,db_trend) <= distance){
				similar_words.add(db_trend);
			}
		}
		Collections.sort(similar_words);
		return similar_words;
	}
	
	public static int levenshteinDistance(String a, String b) {
	        a = a.toLowerCase();
	        b = b.toLowerCase();
	        // i == 0
	        int [] costs = new int [b.length() + 1];
	        for (int j = 0; j < costs.length; j++)
	            costs[j] = j;
	        for (int i = 1; i <= a.length(); i++) {
	            // j == 0; nw = lev(i - 1, j)
	            costs[0] = i;
	            int nw = i - 1;
	            for (int j = 1; j <= b.length(); j++) {
	                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
	                nw = costs[j];
	                costs[j] = cj;
	            }
	        }
	        return costs[b.length()];
	    }
}
